combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two

combinatorial class In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size. Counting sequences and isomorphis ...

es have equal size, by finding a

bijective function In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.

Basic examples

Proving the symmetry of the binomial coefficients

The symmetry of the binomial coefficients states that :

= .

This means that there are exactly as many

combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...

s of things in a set of size as there are combinations of things in a set of size .

A bijective proof

The key idea of the proof may be understood from a simple example: selecting children to be rewarded with ice cream cones, out of a group of children, has exactly the same effect as choosing instead the children to be denied ice cream cones. More abstractly and generally, the two quantities asserted to be equal count the subsets of size and , respectively, of any -element set . Let be the set of all -element subsets of , the set has size

\tbinom.

Let be the set of all subsets of , the set B has size

\tbinom

. There is a simple bijection between the two sets and : it associates every -element subset (that is, a member of ) with its

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...

, which contains precisely the remaining elements of , and hence is a member of . More formally, this can be written using

functional notation In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...

as, defined by for any -element subset of and the complement taken in . To show that f is a bijection, first assume that , that is to say, . Take the complements of each side (in ), using the fact that the complement of a complement of a set is the original set, to obtain . This shows that is one-to-one. Now take any -element subset of in , say . Its complement in , , is a -element subset, and so, an element of . Since , is also

onto In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...

and thus a bijection. The result now follows since the existence of a bijection between these finite sets shows that they have the same size, that is,

\tbinom = \tbinom

Other examples

Problems that admit bijective proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a bijective proof can become very sophisticated. This technique is particularly useful in areas of

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

such as

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, and

number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777� ...

. The most classical examples of bijective proofs in combinatorics include: *

Prüfer sequence In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on ''n'' vertices has length ''n'' − 2, and can be ...

, giving a proof of

Cayley's formula In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^. The formula equivalently counts the number of spanning tr ...

for the number of labeled trees. * Robinson-Schensted algorithm, giving a proof of Burnside's formula for the

symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...

. *

Conjugation Conjugation or conjugate may refer to: Linguistics * Grammatical conjugation, the modification of a verb from its basic form * Emotive conjugation or Russell's conjugation, the use of loaded language Mathematics * Complex conjugation, the chang ...

Young diagram In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups ...

s, giving a proof of a classical result on the number of certain

integer partitions In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same parti ...

. * Bijective proofs of the

pentagonal number theorem In mathematics, the pentagonal number theorem, originally due to Euler, relates the product and series representations of the Euler function. It states that :\prod_^\left(1-x^\right)=\sum_^\left(-1\right)^x^=1+\sum_^\infty(-1)^k\left(x^+x^\right ...

. * Bijective proofs of the formula for the

Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Ca ...

References

External links

*
"Division by three"
' – by Doyle and Conway. *
"A direct bijective proof of the hook-length formula"
' – by Novelli, Pak and Stoyanovsky. *
"Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees"
' – by Gilles Schaeffer. *
"Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials"
' – by

Doron Zeilberger Doron Zeilberger (דורון ציילברגר, born 2 July 1950 in Haifa, Israel) is an Israeli mathematician, known for his work in combinatorics. Education and career He received his doctorate from the Weizmann Institute of Science in 1976, ...

. *
"Partition Bijections, a Survey"
' – by

Igor Pak Igor Pak (russian: link=no, Игорь Пак) (born 1971, Moscow, Soviet Union) is a professor of mathematics at the University of California, Los Angeles, working in combinatorics and discrete probability. He formerly taught at the Massachusetts ...

.
Garsia-Milne Involution Principle
– from

MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Dig ...

. {{DEFAULTSORT:Bijective Proof Enumerative combinatorics Articles containing proofs Mathematical proofs